package com.example.prom.dangwen.y2023.sort;

import com.alibaba.fastjson.JSON;

import java.util.Random;

public class QuickSort01 {

    public static void quickSort(int[] nums, int lo, int hi){
        if (lo >= hi){
            return;
        }

        int index = partition(nums, lo, hi);
        quickSort(nums, lo, index - 1);
        quickSort(nums, index + 1, hi);
    }

    public static int partition(int[] nums, int lo, int hi){
        int random = new Random().nextInt(hi - lo + 1) + lo;
        swap(nums, random, hi);
        int pivot = nums[hi];
        int less = 0;
        int great = 0;
        for (;great < hi; great++){
            if (nums[great] < pivot){
                swap(nums, less, great);
                less++;
            }
        }
        swap(nums, less, hi);
        return less;
    }

    public static void swap(int[] nums, int pivot, int hi){
        int temp = nums[pivot];
        nums[pivot] = nums[hi];
        nums[hi] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,1,1,2,0,0};
//        mergerSort(nums, 0, nums.length - 1, new int[nums.length]);
//        System.out.println(JSON.toJSONString(nums));
        quickSort(nums, 0 , nums.length - 1);
        System.out.println(JSON.toJSONString(nums));
    }
}
